package foundation.图论.最短路;

import java.util.Arrays;
import java.util.Scanner;

/**
 * {@code Bellman-Ford} 算法
 * <p>
 * 解决可以有负权边但是不能有负环（保证最短路存在）的图，单源最短路算法
 * <p>
 * 松弛操作：
 * <p>
 * 假设源点为 {@code A}，从 {@code A} 到任意点 {@code F} 的最短距离为 {@code distance[F]}
 * <p>
 * 假设从点 {@code P} 出发某条边，去往点 {@code S}，边权为 {@code W}
 * <p>
 * 如果发现，{@code distance[P] + W < distance[S]}，也就是通过该边可以让 {@code distance[S]} 变小
 * <p>
 * 那么就说，{@code P} 出发的这条边对点 {@code S} 进行了松弛操作
 * <p>
 * {@code Bellman-Ford} 过程：
 * <ol>
 *     <li>每一轮考察每条边，每条边都尝试进行松弛操作，那么若干点的 {@code distance} 会变小</li>
 *     <li>当某一轮发现不再有松弛操作出现时，算法停止</li>
 * </ol>
 */
public class BellmanFord {
    static int MAXN = 1001;
    static int MAXM = 10001;
    static int INF = Integer.MAX_VALUE;
    static int n, m;
    static int[] dist = new int[MAXN]; // dist[x] 存储 1 到x的最短距离
    static int[][] edge = new int[MAXM][3]; // u -> v w


    public static int ford() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int u = edge[j][0];
                int v = edge[j][1];
                int w = edge[j][2];
                dist[u] = Math.min(dist[u], dist[v] + w);
            }
        }
        if (dist[n] > INF / 2) return -1;
        return dist[n];
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            edge[i][0] = u;
            edge[i][1] = v;
            edge[i][2] = w;
        }
        Arrays.fill(dist, 0, n, INF);
        int ford = ford();
        System.out.println(ford);
    }
}
